package 力扣_二分查找;

/**
 * @author zx
 * @create 2022-08-26 21:32
 */
public class 在排序数组中查找元素的第一个和最后一个位置_34 {
    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[2];
        res[0] = leftBound(nums,target);
        res[1] = rightBound(nums,target);
        return res;
    }
    private int leftBound(int[] arr, int target){
        int left = 0,right = arr.length - 1;
        while(left <= right){
            int mid = left + ((right - left) >> 1);
            if(arr[mid] > target){
                right = mid - 1;
            }else if(arr[mid] < target){
                left = mid + 1;
            }else if(arr[mid] == target){
                right = mid - 1;
            }
        }
        if(left >= arr.length || arr[left] != target){
            return -1;
        }
        return left;
    }
    private int rightBound(int[] arr, int target){
        int left = 0,right = arr.length - 1;
        while(left <= right){
            int mid = left + ((right - left) >> 1);
            if(arr[mid] > target){
                right = mid - 1;
            }else if(arr[mid] < target){
                left = mid + 1;
            }else if(arr[mid] == target){
                left = mid + 1;
            }
        }
        if(right < 0 || arr[right] != target){
            return -1;
        }
        return right;
    }
}
